#include<iostream>
using namespace std;
#define size 10

/**
 * @brief 图邻接矩阵
 */
template<typename DT>
class AMGraph
{
private:
	int NumVertex;  //图中的顶点数；
	int NumEdge;    //图中边的数量；
	int vertex[size];  //存放顶点 
    int arc[size][size];

	
public:
    int VertexIndex(DT v)  //查找顶点的下标
    {
        for (int i = 0; i < NumVertex; i++)
        {
            if (vertex[i] == v)
                return i;
        }
        return -1;
    }

	AMGraph(DT vertexdata[], int v, int e)  //构建一个有v个顶点，e条边的图，其中顶点存放的数据是vertexdata中的值
	{
        cout<<"Enter (u,v,w), where u and v are the two vertices of the edge and w is the weight of the edge (u,v)"<<endl;
		NumVertex = v;
        NumEdge = e;

		int i,j;
		for(i = 0 ; i < NumVertex ; i++)
			vertex[i] = vertexdata[i];
        
        //初始化邻接矩阵,0表示两点间没有路径
		for(i = 0 ; i < NumVertex ; i++)
		{
			for(j = 0 ; j < NumVertex ; j++)
				arc[i][j] = 0;  
		}

        //输入边的两个顶点和权重，直到边的数量达到边总数为止，以换行符分隔每次输入.
        for (int k = 0; k < NumEdge; k++)
        {
            DT i, j;
            int w;
            std::cin >> i >> j >> w; 
            int p1=VertexIndex(i);
            int p2=VertexIndex(j);
            arc[p1][p2] = w;      
        }
    };
    
    void listVertexes() //输出每个顶点
    {
        cout<<"The Vertex of AMGraph are as follows: ";
        for (int i = 0; i < NumVertex; i++)
        {
            cout<<vertex[i]<<" ";
        }
        cout<<endl;

    }
    void listEdges()  //输出每一条边（u，v，w）
    {
        cout<<"The Edge of AMGraph are as follows: "<<endl;
        for (int i = 0; i < NumVertex; i++)
        {
            for(int j = 0 ; j < NumVertex ; j++)
            {
                if(arc[i][j] != 0)
				    cout<<"("<<vertex[i]<<","<<vertex[j]<<","<<arc[i][j]<<")  ";
			}
            
        }
        cout<<endl;
    }

    void Show() //输出邻接矩阵
    {
        cout<<"The Adjacent Matrix Graph is as follows:"<<endl;
        int i,j;
        cout<<"      ";
        for (i = 0; i < NumVertex; i++)
        {
            cout<<vertex[i]<<"     ";
        }
        cout<<endl;
        for (i = 0; i < NumVertex; i++)
        {
            cout<<vertex[i]<<"     ";
            for (j = 0; j < NumVertex; j++)
                cout<<arc[i][j]<<"     ";
            cout<<endl;
        }
    }


    void InsertVertex(DT v); //插入一个顶点v
    void InsertEdge(DT v1, DT v2, int w); //插入一条由点v1和v2组成的边
    int GetEdgeNum(DT v); //获取与顶点v相连的顶点总数
    void DeleteVertex(DT v); //删除一个顶点
    void DeleteEdge(DT v1,DT v2); //删除顶点v1和v2之间的边
    ~AMGraph(){};
};



/**
 * @brief 邻接表
 */

// 定义边表结点
struct ArcNode
{
    int adjvex; //这个索引值是边表节点自己在数组中的索引值
    ArcNode* next; //指向下一个边表节点；
    int Weight;
};
// 定义顶点表结点
struct VertexNode
{
    int vertex; //表示顶点的名字
    ArcNode* firstedge;
};

// 基于邻接表存储结构的图的类实现
const int MaxSize = 10;
template<class DT>
class ALGraph
{
public:
    int VertexIndex(DT v)  //查找顶点的下标
    {
        for (int i = 0; i < vertexNum; i++)
        {
            if (adjlist[i].vertex == v)
                return i;
        }
        return -1;
    }
    ALGraph(DT a[], int n, int e);// 构造函数建立具有n个定点e条边的图
    ~ALGraph() {}// 析构函数
    void listVertexes(); //输出所有顶点
    void listEdges(); //输出所有边及权重；
    void Show(); //输出邻接表；
private:
    VertexNode adjlist[MaxSize];// 存放顶点表结点的数组
    int vertexNum, arcNum;// 图中顶点数和边数
};

template<class DT>
ALGraph<DT>::ALGraph(DT a[], int n, int e)
{
    cout<<"Enter (u,v,w), where u and v are the two vertices of the edge and w is the weight of the edge (u,v)"<<endl;
    vertexNum = n;
    arcNum = e;
    for (int i = 0; i <vertexNum; i++)
    {
        adjlist[i].vertex = a[i];
        adjlist[i].firstedge = NULL;
    }
    for (int k = 0; k < arcNum; k++)
    {
        DT i, j;
        int w;
        std::cin >> i >> j >> w;
        int p1 = VertexIndex(i); //获取i在顶点表中的下标
        int p2 = VertexIndex(j);
        ArcNode* s = new ArcNode;
        s->adjvex = j;
        s->Weight = w;
        s->next = adjlist[p1].firstedge; //把新插入的顶点下标连在顶点后
        adjlist[p1].firstedge = s;
    }
}

template<class DT>
void ALGraph<DT>::listVertexes()
{
    cout<<"The Vertex of Graph are as follows: ";
    for (int i = 0; i < vertexNum; i++)
    {
        cout<<adjlist[i].vertex<<" ";
    }
    cout<<endl;
}

template<class DT>
void ALGraph<DT>::listEdges()
{
    cout<<"The Edge of Graph are as follows: "<<endl;
    for (int i = 0; i < vertexNum; i++)
    {
        if (adjlist[i].firstedge != NULL)
        {
            ArcNode *p = adjlist[i].firstedge;
            while (p != NULL)
            {
            cout<<"("<<adjlist[i].vertex<<",";
            DT j = p->adjvex;
            int q = VertexIndex(j);
            cout<<adjlist[q].vertex<<","<<p->Weight<<") ";
            p = p->next;
            }
        }
        
    }
    
    
    cout<<endl;
}

template<class DT>
void ALGraph<DT>::Show()
{
    cout<<"The Adjacent List Graph is as follows:"<<endl;
    for (int i=0;i<vertexNum;i++)
    {
        cout<<adjlist[i].vertex;
        ArcNode *p = adjlist[i].firstedge;
        while(p)
        {
            cout<<"-("<<p->Weight<<")->";
            cout<<p->adjvex;
            p = p->next;
        }
        cout<<"->NULL"<<endl;
    }
}